- Title
- From expanded digraphs to lifts of voltage digraphs and line digraphs
- Creator
- Dalfó, C.; Fiol, M. A.; Miller, M.; Ryan, J.
- Relation
- Australasian Journal of Combinatorics Vol. 69, Issue 3, p. 323-333
- Relation
- https://ajc.maths.uq.edu.au/?page=get_volumes&volume=69#
- Publisher
- Centre for Discrete Mathematics & Computing, University of Queensland
- Resource Type
- journal article
- Date
- 2017
- Description
- In this note we present a general approach to construct large digraphs from small ones. These are called expanded digraphs, and, as particular cases, we show the close relationship between lifted digraphs of voltage digraphs and line digraphs, which are two known ways to obtain dense digraphs. In the same context, we show the equivalence between the vertex-splitting and partial line digraph techniques. Then, we give a sufficient condition for a lifted digraph of a base line digraph to be again a line digraph. Some of the results are illustrated with two well-known families of digraphs, namely, the De Bruijn and Kautz digraphs, where it is shown that both families can be seen as lifts of smaller De Bruijn digraphs with appropriate voltage assignments.
- Subject
- voltage digraphs; vertex-splitting; De Bruijn digraphs; Kautz digraphs
- Identifier
- http://hdl.handle.net/1959.13/1349258
- Identifier
- uon:30378
- Identifier
- ISSN:1034-4942
- Rights
- © Copyright 2017 Combinatorial Mathematics Society of Australasia (Inc.) Any individual is entitled to download a copy of any paper from this site for purposes of individual study or research.
- Language
- eng
- Full Text
- Reviewed
- Hits: 4835
- Visitors: 3169
- Downloads: 204
Thumbnail | File | Description | Size | Format | |||
---|---|---|---|---|---|---|---|
View Details Download | ATTACHMENT02 | Publisher version (open access) | 270 KB | Adobe Acrobat PDF | View Details Download |